import java.math.BigInteger;
import java.util.HashMap;
import java.util.Random;

// 测试
public class CRT_Multi_Threshold_Multi_Secret_Sharing_CorrectnessTestVers {

    private static final Random RND = new Random();

    // 安全参数，按比特位算
    private final int parameter;

    // 总共的秘密个数
    private final int secretsNums;

    // 总共的秘密子份额数量
    private final int sharingNums;
    // 能够正常恢复秘密的门限值数组
    private final int[] thresholds;

    // 所要共享的秘密数组
    private final BigInteger[] secrets;
    //
    private final BigInteger[] qs;
    // 秘密子份额数组
    private final BigInteger[] subSecrets;

    /**
     * 构造函数
     *
     * @param secretsNums 总共要共享的秘密的个数
     * @param sharingNums 要分享的子秘密的总数
     * @param thresholds  门限数组，恢复各个秘密所需的门限值
     * @param parameter   安全参数
     */
    public CRT_Multi_Threshold_Multi_Secret_Sharing_CorrectnessTestVers(int secretsNums, int sharingNums, int[] thresholds, int parameter) {
        this.secretsNums = secretsNums;
        this.sharingNums = sharingNums;
        this.thresholds = thresholds;
        this.parameter = parameter;

        secrets = new BigInteger[secretsNums];
        for (int i = 0; i < secretsNums; i++) {
            secrets[i] = new BigInteger(this.parameter, RND);
        }
        qs = new BigInteger[secretsNums];
        subSecrets = new BigInteger[sharingNums];
    }

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            CRT_Multi_Threshold_Multi_Secret_Sharing_CorrectnessTestVers tss = new CRT_Multi_Threshold_Multi_Secret_Sharing_CorrectnessTestVers(3, 30, new int[]{2, 4, 7}, 500);
            tss.secretDistribute();
            int successTime = 0, testTime = 100;
            for (int j = 0; j < testTime; j++) {
                // 每次都是在 [1, 子秘密份额总数 + 1) 上随机选择1个整数，作为拥有的子份额
                if (tss.secretReconstruction(RND.nextInt(tss.sharingNums + 1))) {
                    successTime++;
                }
            }
            System.out.println("第" + (i + 1) + "次秘密共享的" + "秘密重构的正确率为：" + successTime * 1.0 / testTime * 100 + "%");
        }
    }

    public void secretDistribute() {
        // 秘密分发过程
        // 1.选择m个互不相同的素数q1 < q2 < ... < qm，要注意满足 秘密 qi > ki
        for (int i = 0; i < secretsNums; i++) {
            // 获取素数 qi
            qs[i] = BigInteger.probablePrime(parameter, RND);
            if (qs[i].compareTo(secrets[i]) <= 0 || (i >= 1 && qs[i].compareTo(qs[i - 1]) <= 0)) {
                i--;
            }
        }

        // 2.在[1,q1]上任意选择n个不同的整数x1 ... xn分别作为参与者P1 ... Pn的公开身份标识信息
        // 分别选 1,2, ... ,n

        int coefficientNum = thresholds[thresholds.length - 1];
        BigInteger[] coefficientA = new BigInteger[coefficientNum];

        // 3.解恒等式的解，将其记为a0
        coefficientA[0] = crt(secrets, qs, secrets.length);

        // 4.1 先随机选择 t1-1 个整数，并且满足 1 < a1 , a2 , ... , at1-1 < M
        BigInteger M = BigInteger.ONE;
        for (BigInteger q : qs) {
            M = M.multiply(q);
        }
        for (int i = 1; i <= thresholds[0] - 1; i++) {
            coefficientA[i] = new BigInteger(parameter, RND);
            if (coefficientA[i].compareTo(M) >= 0 && coefficientA[i].compareTo(BigInteger.ONE) <= 0) {
                i--;
            }
        }

        // 4.2 对于每个门限值，分别进行类似 [t1, t2 - 1]， [t2, t3 - 1] 这样的运算
        BigInteger accumQ = BigInteger.ONE;
        for (int i = 0; i <= thresholds.length - 2; i++) {
            accumQ = accumQ.multiply(qs[i]);
            for (int j = thresholds[i]; j <= thresholds[i + 1] - 1; j++) {
                // cj是在[1, qi - 1]之间的任意一个整数
                BigInteger cj = new BigInteger(parameter, RND);
                while (cj.compareTo(qs[i]) >= 0) {
                    cj = new BigInteger(parameter, RND);
                }
                // rj是任意的非零整数
                BigInteger rj = new BigInteger(parameter, RND);
                // 填入coefficientA
                coefficientA[j] = cj.multiply(rj).multiply(accumQ).mod(M);
            }
        }

        // 5. 计算每个参与者的份额 yi = H(xi) mod M
        for (int i = 0; i < sharingNums; i++) {
            BigInteger x = BigInteger.valueOf(i + 1);
            subSecrets[i] = BigInteger.ZERO;
            for (int j = 0; j < coefficientA.length; j++) {
                subSecrets[i] = subSecrets[i].add(coefficientA[j].multiply(x.pow(j)));
            }
        }
    }

    public boolean secretReconstruction(int recoverNum) {
        // 秘密重构过程
        int[] xs = new int[recoverNum];
        BigInteger[] ys = new BigInteger[recoverNum];

        // 随机选取recoverNum个数，开1个map进行去重
        HashMap<Integer, Boolean> map = new HashMap<>();
        for (int i = 0; i < recoverNum; i++) {
            // 随机选某个秘密
            int x = RND.nextInt(recoverNum + 1);
            if (x == 0 || map.get(x) != null) {
                // 说明已经有这个数
                i--;
                continue;
            }
            map.put(x, Boolean.TRUE);
            xs[i] = x;
            ys[i] = new BigInteger(subSecrets[x - 1].toString());
        }

        boolean flag = true;
        for (int i = 0; i < secretsNums; i++) {
            BigInteger lagrange = lagrange(xs, ys, qs[i]);
            BigInteger anySecret = lagrange.mod(qs[i]);
            if (anySecret.equals(secrets[i]) != (recoverNum >= thresholds[i])) {
                flag = false;
                break;
            }
        }
        return flag;
    }

    // 拉格朗日插值公式
    private BigInteger lagrange(int[] xs, BigInteger[] ys, BigInteger qi) {
        // 计算当x=0的时候即可恢复秘密
        BigInteger res = BigInteger.ZERO;
        BigInteger one;
        BigInteger diviNum;
        for (int i = 0; i < xs.length; i++) {
            one = BigInteger.ONE;
            diviNum = BigInteger.ONE;
            for (int j = 0; j < xs.length; j++) {
                if (j == i) continue;
                one = one.multiply(new BigInteger(String.valueOf(-xs[j])));
                diviNum = diviNum.multiply(BigInteger.valueOf(xs[i] - xs[j]));
            }
            one = one.multiply(diviNum.modInverse(qi));
            one = one.multiply(ys[i]);
            res = res.add(one);
        }
        return res;
    }

    // 中国剩余定理的计算公式
    private BigInteger crt(BigInteger[] a, BigInteger[] p, int num) {
        // 余数数组是a，模数数组是p，方程个数是num
        BigInteger P = BigInteger.ONE;
        for (int i = 0; i < num; i++) {
            P = P.multiply(p[i]);
        }
        BigInteger result = BigInteger.ZERO;
        // 生成逆元数组
        BigInteger[] PInv = new BigInteger[num];
        for (int i = 0; i < num; i++) {
            PInv[i] = P.divide(p[i]).modInverse(p[i]);
            result = result.add(P.divide(p[i]).multiply(PInv[i]).multiply(a[i]));
        }
        return result.mod(P);
    }

}
